package flare.analytics.cluster
{
  import flare.animate.Transitioner;
  import flare.util.math.IMatrix;
  import flare.vis.data.DataList;

  /**
   * Hierarchically clusters a network based on inferred community structure.
   * The result is a cluster tree in which each merge is chosen so as to
   * maximize within-cluster linkage while minimizing between-cluster linkage.
   * This class uses <a href="http://arxiv.org/abs/cond-mat/0309508">Newman's
   * fast algorithm for detecting community structure</a>. Optionally allows
   * clients to provide an edge weight function indicating the strength of
   * ties within the network.
   */
  public class CommunityStructure extends HierarchicalCluster
  {
    /** A function defining edge weights in the graph. */
    public var edgeWeights:Function = null;

    // --------------------------------------------------------------------

    /**
     * Creates a new community structure instance
     */
    public function CommunityStructure()
    {
    }

    /** @inheritDoc */
    public override function operate(t:Transitioner = null):void
    {
      calculate(visualization.data.group(group), edgeWeights);
    }

    /**
     * Calculates the community structure clustering. As a result of this
     * method, a cluster tree will be computed and graph nodes will be
     * annotated with both community and sequence indices.
     * @param list the data list to cluster
     * @param w an edge weighting function. If null, each edge will be
     *  given weight one.
     */
    public function calculate(list:DataList, w:Function = null):void
    {
      compute(list.adjacencyMatrix(w));
      _tree = buildTree(list);
      labelNodes();
    }

    /** Computes the clustering */
    private function compute(G:IMatrix):void
    {
      _merges = new MergeEdge(-1, -1);
      _qvals = [];
      _size = G.rows;
      var i:int, j:int, k:int, s:int, t:int, v:Number;
      var Q:Number = 0, Qmax:Number = 0, dQ:Number, dQmax:Number = 0, imax:int;

      // initialize normalized matrix
      var N:int = G.rows, Z:IMatrix = G.clone();

      for(i = 0; i < N; ++i)
      Z.set(i, i, 0);     // clear diagonal
      Z.scale(1 / Z.sum); // normalize matrix

      // initialize column sums and edge list
      var E:MergeEdge = new MergeEdge(-1, -1);
      var e:MergeEdge = E, m:MergeEdge = _merges;
      var eMax:MergeEdge = new MergeEdge(0, 0);
      var A:Array = new Array(N);

      for(i = 0; i < N; ++i)
      {
        A[i] = 0;

        for(j = 0; j < N; ++j)
        {
          if((v = Z.get(i, j)) != 0)
          {
            A[i] += v;
            e = e.add(new MergeEdge(i, j));
          }
        }
      }

      // run the clustering algorithm
      for(var ii:int = 0; ii < N - 1 && E.next; ++ii)
      {
        dQmax = Number.NEGATIVE_INFINITY;
        eMax.update(0, 0);

        // find the edge to merge
        for(e = E.next; e != null; e = e.next)
        {
          i = e.i;
          j = e.j;

          if(i == j)continue;
          dQ = Z.get(i, j) + Z.get(j, i) - 2 * A[i] * A[j];

          if(dQ > dQmax)
          {
            dQmax = dQ;
            eMax.update(i, j);
          }
        }

        // perform merge on graph
        i = eMax.i;
        j = eMax.j;

        if(j < i)
        {
          i = eMax.j;
          j = eMax.i;
        }
        var na:Number = 0;

        for(k = 0; k < N; ++k)
        {
          v = Z.get(i, k) + Z.get(j, k);

          if(v != 0)
          {
            na += v;
            Z.set(i, k, v);
            Z.set(j, k, 0);
          }
        }

        for(k = 0; k < N; ++k)
        {
          v = Z.get(k, i) + Z.get(k, j);

          if(v != 0)
          {
            Z.set(k, i, v);
            Z.set(k, j, 0);
          }
        }
        A[i] = na;
        A[j] = 0;

        for(e = E.next; e != null; e = e.next)
        {
          s = e.i;
          t = e.j;

          if((i == s && j == t) || (i == t && j == s))
          {
            e.remove();
          }

          else if(s == j)
          {
            e.i = i;
          }

          else if(t == j)
          {
            e.j = i;
          }
        }

        Q += dQmax;

        if(Q > Qmax)
        {
          Qmax = Q;
          imax = ii;
        }
        _qvals.push(Q);
        m = m.add(new MergeEdge(i, j));
      }
    }
  } // end of class CommunityStructure
}